#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: go_maze.py 
@version:
@time: 2024/01/28

起点与终点是固定的，并且需要返回路径。

对于每个节点来说，其只有上下左右4个子节点，因此采用广度优先搜索算法来遍历每个节点可到达的4个方位。

另外，需要定义一个二维数组，将每一个节点的上一步节点记录下来；
定一个二维数组，保存每个节点是否被访问，已经被访问过的节点不再访问。

最终从出口处逆向搜索，直至到达入口为止。
"""

from collections import deque


def go_maze(maze):
    length = len(maze)  # 迷宫长度
    width = len(maze[0])  # 迷宫宽度
    visited = [[0 for _ in range(width)] for _ in range(length)]  # 表示每个节点是否被访问过的二维列表
    step = [[(-1, -1) for _ in range(width)] for _ in range(length)]  # 表示路径子节点与父节点的关系
    direction = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    queue = deque([(0, 0)])
    visited[0][0] = 1
    result = []  # 表示存储结果的列表，存储路径
    while queue:
        x, y = queue.popleft()
        # 到达迷宫终点，结束循环
        if x == length - 1 and y == width - 1:
            break
        # 朝着四个方向尝试
        for d in direction:
            x1 = x + d[0]
            y1 = y + d[1]
            # 超出迷宫界限，且访问过，且节点为1，跳过当前循环
            if x1 < 0 or y1 < 0 or x1 >= length or y1 >= width or \
                    visited[x1][y1] == 1 or maze[x1][y1] == 1:
                continue
            step[x1][y1] = (x, y)  # 子节点与父节点的关系
            visited[x1][y1] = 1  # 标记当前节点被访问
            queue.append((x1, y1))  # 将当前节点加入队列中
    # 在迭代过程执行完毕后，需要判断入口与出口之间是否有路可走，若step中对应的出口节点值未发生变化，
    # 仍然是初始值(-1,-1)，那么判定为无路可走，返回False。
    if step[length - 1][width - 1] == (-1, -1):
        return False
    # 为了将路径保存在result列表中，需要在step数组中从出口向入口逆向查找
    re_x = length - 1
    re_y = width - 1
    result.append((re_x, re_y))
    while re_x or re_y:
        re_x, re_y = step[re_x][re_y]
        result.append((re_x, re_y))
    return result[::-1]


maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
]
print(res := go_maze(maze))

assert res == [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]
